Much of data handled in computer systems is managed by databases. As the amount of data stored in a database increases, time required for data retrieval becomes longer. For example, if data is all scanned and data which meets a retrieval condition is extracted, the calculation time required is O(N) in O notation (N is the number of pieces of data and is an integer greater than or equal to 1). Accordingly, in order to make database retrieval efficient, index data (index), for example, for data stored in a database is generated. By building an index, calculation time is reduced to about O(logN).
For example, a value (index value) which is a key for a piece of data in a database and location information for the piece of data are associated with each other and are registered in an index. In order to retrieve from a database having an index, an index value corresponding to a retrieval key is retrieved from the index. Data is acquired on the basis of location information for the data associated with the key, and is outputted as a retrieval result.
When data in such a database having an index is updated, the index is updated. This makes it possible to quickly find data after update at retrieval time. Accordingly, an automatic index update apparatus which automatically builds and deletes an index is proposed. Each time an attribute of data to be retrieved is accessed, the apparatus updates access frequency information for the attribute. The apparatus evaluates on the basis of the access frequency information whether to update the contents of an index, and updates the contents of the index on the basis of an evaluation result.
Japanese Laid-open Patent Publication No. 06-215037
An index is structured by the use of, for example, a tree structure so that high-speed retrieval can be performed. Therefore, in an index update process not only is an index value added, changed, or deleted, but the data structure of an index is rebuilt. If the data structure of an index is rebuilt each time data in a database is updated, a processing load on an entire system is excessive. Accordingly, for example, the following method may be adopted. An index is not updated at record update time and an index update process is performed at the time of the next retrieval. This prevents index update from occurring frequently, and increases the efficiency of processing by the entire system.
However, if an index is updated at retrieval time, time required for a response to a retrieval request depends on the number of records for which the index is not yet updated, and there are variations in response time at retrieval time. For example, time required for a response to a retrieval request inputted after update of a large amount of data is far longer than time required for a response to another retrieval request.